문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 혼합 계산 (문단 편집) === 수식 [[트리(그래프)|트리]]를 이용한 혼합 계산 === [[파일:혼합계산1.png]] 혼합 계산을 위와 같이 이진 트리 구조로 나타낼 수도 있는데, 이것을 수식 트리(Expression Tree, Parse Tree)라고 한다. 수식 트리를 [[트리(그래프)#s-4.1.1|중위 순회]] 방법으로 순회하여 방문한 각 노드의 내용을 차례대로 쓰고, 하위 노드가 있는 각 노드에 대하여 그 노드와 하위 노드에 해당하는 내용을 괄호로 묶으면 계산식이 된다. 예를 들어 위와 같은 경우, 계산식은 (2+(1*2))*(3+(2*4))가 된다. 즉, 혼합 계산식에서의 괄호가 위의 트리 구조에서 하위 노드가 있는 각 노드에 해당하는 것이다. 단, 여기서 (1*2), (2*4)의 괄호처럼 일부 괄호를 생략해도 수학적으로 올바른 계산식이 도출될 수 있다. 수식 트리의 주요 특징은 다음과 같다. * 리프 노드(leaf node)가 아닌 노드에는 연산 기호가 들어간다. * 리프 노드에는 숫자나 문자 등 피연산자가 들어간다. 수식 트리를 후위 순회한 결과로 나온 문자열을 [[스택(자료구조)|스택]]을 이용하여 수식처럼 계산할 수 있다. 예를 들어 위와 같은 경우에는 후위 순회한 결과가 212*+324*+*인데, 다음과 같은 규칙을 이용한다. * 수식의 왼쪽부터 한 문자씩 탐색한다. * 탐색한 문자가 피연산자이면 그것을 스택에 push한다. * 탐색한 문자가 연산 기호이면 스택에서 2번 연속 pop하고, 그 값을 각각 a, b라 하자. a와 b를 그 연산 기호로 연산한 값을 push한다. 여기서 '''pop의 순서는 b → a'''가 되어야 한다는 점에 주의해야 한다. * 마지막에는 스택에 하나의 값이 남는데, 그 값이 바로 결과값이다. 이 방법으로 212*+324*+*를 계산하면 다음과 같다. || '''{{{#008000 탐색하는 문자}}}''' || '''{{{#008000 설명}}}''' || '''{{{#008000 스택}}}''' || || 2 ||<|3> 숫자이므로 push ||2 || || 1 ||2 1 || || 2 ||2 1 2 || || * || 2번 연속 pop 후 1*2=2를 push ||2 2 || || + || 2번 연속 pop 후 2+2=4를 push ||4 || || 3 ||<|3> 숫자이므로 push ||4 3 || || 2 ||4 3 2 || || 4 ||4 3 2 4 || || * || 2번 연속 pop 후 2*4=8를 push ||4 3 8 || || + || 2번 연속 pop 후 3+8=11을 push ||4 11 || || * || 2번 연속 pop 후 4*11=44를 push ||44 || 여기서 스택에는 마지막에 하나의 값만 남아야 하고, 숫자를 만날 때마다 스택의 항목 수가 1 증가하고, 연산 기호를 만날 때마다 1 감소하므로 수식에서 숫자의 개수는 (연산 기호의 개수+1)이어야 한다는 것을 알 수 있다. 또한 왼쪽부터 문자를 탐색하면서 만난 숫자의 개수가 연산 기호의 개수보다 같거나 많은 적이 없어야 한다. 이 방법을 사용하면 모든 종류의 이항연산자를 동일한 방식으로 취급할 수 있다. 다만, 단항연산자(논리 부정, 여집합 등등)이나 삼항 연산자 등을 처리하기 위해서는 이를 수정해서 사용해야 한다.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기